
Iterative Scaling and Coordinate Descent Methods for Maximum Entropy Models
Maximum entropy (Maxent) is useful in natural language processing and many other areas. Iterative scaling (IS) methods are one of the most popular approaches to solve Maxent. With many variants of IS methods, it is difficult to understand them and see the differences. In this paper, we create a general and unified framework for iterative scaling methods. This framework also connects iterative scaling and coordinate descent methods. We prove general convergence results of IS methods and analyze their computational complexity. Based on the proposed framework, we extend a coordinate descent method for linear SVM to Maxent. Results show that it is faster than existing iterative scaling methods.
Parallel Spectral Clustering.
Abstract. Spectral clustering algorithm has been shown to be more effective in finding clusters than most traditional algorithms. However, spectral clustering suffers from a scalability problem in both memory use and computational time when a dataset size is large. To perform clustering on large datasets, we propose to parallelize both memory use and computation on distributed computers. Through an empirical study on a large document dataset of 193, 844 data instances and a large photo dataset of 637, 137, we demonstrate that our parallel algorithm can effectively alleviate the scalability problem. Key words: Parallel spectral clustering, distributed computing 1
A dual coordinate descent method for large%2Dscale linear SVM.
In many applications, data appear with a huge number of instances as well as features. Linear Support Vector Machines (SVM) is one of the most popular tools to deal with such large-scale sparse data. This paper presents a novel dual coordinate descent method for linear SVM with L1- and L2loss functions. The proposed method is simple and reaches an ɛ-accurate solution in O(log(1/ɛ)) iterations. Experiments indicate that our method is much faster than state of the art solvers such as Pegasos, TRON, SVM perf, and a recent primal coordinate descent implementation. 1.
A sequential dual method for large scale multi%2Dclass linear svms.
Efficient training of direct multi-class formulations of linear Support Vector Machines is very useful in applications such as text classification with a huge number examples as well as features. This paper presents a fast dual method for this training. The main idea is to sequentially traverse through the training set and optimize the dual variables associated with one example at a time. The speed of training is enhanced further by shrinking and cooling heuristics. Experiments indicate that our method is much faster than state of the art solvers such as bundle, cutting plane and exponentiated gradient methods.
Cross%2Dgeneration and cross%2Dlaboratory predictions of Affymetrix microarrays by rank%2Dbased methods.

Coordinate Descent Method for Large%2Dscale L2%2Dloss Linear Support Vector Machines.

LIBLINEAR A Library for Large Linear Classification.
LIBLINEAR is an open source library for large-scale linear classification. It supports logistic regression and linear support vector machines. We provide easy-to-use command-line tools and library calls for users and developers. Comprehensive documents are available for both beginners and advanced users. Experiments demonstrate that LIBLINEAR is very efficient on large sparse data sets.
Trust Region Newton Method for Logistic Regression.

Trust region Newton methods for large%2Dscale logistic regression.
Large-scale logistic regression arises in many applications such as document classification and natural language processing. In this paper, we apply a trust region Newton method to maximize the log-likelihood of the logistic regression model. The proposed method uses only approximate Newton steps in the beginning, but achieves fast convergence in the end. Experiments show that it is faster than the commonly used quasi Newton approach for logistic regression. We also compare it with existing linear SVM implementations. 1
The NTU Toolkit and Framework for High%2DLevel Feature Detection at TRECVID 2007.

On the Convergence of Multiplicative Update Algorithms for Nonnegative Matrix Factorization.

On the Convergence of Multiplicative Update Algorithms for Nonnegative Matrix Factorization.



Projected Gradient Methods for Nonnegative Matrix Factorization.

Ranking individuals by group comparisons.

A study on SMO%2Dtype decomposition methods for support vector machines.
Decomposition methods are currently one of the major methods for training support vector ma-chines. They vary mainly according to different working set selections. Existing implementations and analysis usually consider some specific selection rules. In this article, we study Sequential Minimal Optimization (SMO)-type decomposition methods under a general and flexible way of choosing the two-element working set. Main results include: 1) a simple asymptotic convergence proof, 2) a general explanation of the shrinking and caching techniques, and 3) the linear convergence of the method. Extensions to some SVM variants are also discussed. I.
Generalized Bradley%2DTerry Models and Multi%2DClass Probability Estimates.
Editor: The Bradley-Terry model for obtaining individual skill from paired comparisons has been popular in many areas. In machine learning, this model is related to multi-class probability estimates by coupling all pairwise classification results. Error correcting output codes (ECOC) are a general framework to decompose a multi-class problem to several binary problems. To obtain probability estimates under this framework, this paper introduces a generalized Bradley-Terry model in which paired individual comparisons are extended to paired team comparisons. We propose a simple algorithm with convergence proofs to solve the model and obtain individual skill. Experiments on synthetic and real data demonstrate that the algorithm is useful for obtaining multi-class probability estimates. Moreover, we discuss four extensions of the proposed model: 1) weighted individual skill, 2) home-field advantage, 3) ties, and 4) comparisons with more than two teams. Keywords: Bradley-Terry model, Probability estimates, Error correcting output codes, Support Vector Machines
Training Support Vector Machines via SMO%2DType Decomposition Methods.

Training Support Vector Machines via SMO%2DType Decomposition Methods.

Working Set Selection Using Second Order Information for Training Support Vector Machines.
Working set selection is an important step in decomposition methods for training support vector machines (SVMs). This paper develops a new technique for working set selection in SMO-type decomposition methods. It uses second order information to achieve fast convergence. Theoretical properties such as linear convergence are established. Experiments demonstrate that the proposed method is faster than existing selection methods using first order information.
Leave%2DOne%2DOut Bounds for Support Vector Regression Model Selection.
Minimizing bounds of leave-one-out (loo) errors is an important and e#cient approach for support vector machine (SVM) model selection. Past research focuses on their use for classification but not regression. In this article, we derive loo bounds for support vector regression (SVR) and discuss the di#erence from those for classification. Experiments demonstrate that the proposed bounds are competitive with Bayesian SVR for parameter selection. We also discuss the di#erentiability of loo bounds. 1 
A Generalized Bradley%2DTerry Model From Group Competition to Individual Skill.

Probability Estimates for Multi%2Dclass Classification by Pairwise Coupling.
Pairwise coupling is a popular multi-class classification method that combines together all  pairwise comparisons for each pair of classes. This paper presents two approaches for obtaining  class probabilities. Both methods can be reduced to linear systems and are easy to implement.
Decomposition Methods for Linear Support Vector Machines.

Probability Estimates for Multi%2DClass Classification by Pairwise Coupling.
Pairwise coupling is a popular multi-class classification method that combines together all  pairwise comparisons for each pair of classes. This paper presents two approaches for obtaining  class probabilities. Both methods can be reduced to linear systems and are easy to implement.
Radius Margin Bounds for Support Vector Machines with the RBF Kernel.

Asymptotic Behaviors of Support Vector Machines with Gaussian Kernel.
Support vector machines (SVMs) with the Gaussian (RBF) kernel have been popular for practical use. Model selection in this class of SVMs involves two hyperparameters: the penalty parameter C and the kernel width σ. This paper analyzes the behavior of the SVM classifier when these hyperparameters take very small or very large values. Our results help in a good understanding of the hyperparameter space that leads to an efficient heuristic method of searching for hyperparameter values with small generalization errors. The analysis also indicates that if complete model selection using the Gaussian kernel has been conducted, there is no need to consider linear SVM. 1
Special issue on support vector machines.

Analysis of Nonstationary Time Series Using Support Vector Machines.
Time series from alternating dynamics have many important  applications. In [5], the authors propose an approach to solve the drifting  dynamics. Their method directly solves a non-convex optimization  problem. In this paper, we propose a strategy which solves a sequence of  convex optimization problems by using modi  ed support vector regression.
Analysis of Nonstationary Time Series Using Support Vector Machines.
Time series from alternating dynamics have many important  applications. In [5], the authors propose an approach to solve the drifting  dynamics. Their method directly solves a non-convex optimization  problem. In this paper, we propose a strategy which solves a sequence of  convex optimization problems by using modi  ed support vector regression.
A Simple Decomposition Method for Support Vector Machines.
Abstract. The decomposition method is currently one of the major methods for solving support vector machines. An important issue of this method is the selection of working sets. In this paper through the design of decomposition methods for bound-constrained SVM formulations we demonstrate that the working set selection is not a trivial task. Then from the experimental analysis we propose a simple selection of the working set which leads to faster convergences for difficult cases. Numerical experiments on different types of problems are conducted to demonstrate the viability of the proposed method.
A Simple Decomposition Method for Support Vector Machines.
Abstract. The decomposition method is currently one of the major methods for solving support vector machines. An important issue of this method is the selection of working sets. In this paper through the design of decomposition methods for bound-constrained SVM formulations we demonstrate that the working set selection is not a trivial task. Then from the experimental analysis we propose a simple selection of the working set which leads to faster convergences for difficult cases. Numerical experiments on different types of problems are conducted to demonstrate the viability of the proposed method.


Training v %2DSupport Vector Regression Theory and Algorithms.

Solving General Capacity Problem by Relaxed Cutting Plane Approach.

Optical Coating Designs Using the Family Competition Evolutionary Algorithm.

Formulations of Support Vector Machines A Note from an Optimization Point of View.
In this paper, we discuss issues about formulations of support vector machines (SVM) from an optimization point of view. First, support vector machines map training data into a higher (may be infinite) dimensional space. Currently primal and dual formulations of SVM are derived in the finite dimensional space and readily extended to the infinite dimensional space. We rigorously discuss the primal-dual relation in the infinite dimensional spaces. Second, SVM formulations contain penalty terms which are different from unconstrained penalty functions in optimization. Traditionally unconstrained penalty functions approximate a constrained problem as the penalty parameter increases. We are interested in similar properties for SVM formulations. For two of the most popular SVM formulations, we show that one enjoys properties of exact penalty functions but the other is only like traditional penalty functions which converge when the penalty parameter goes to infinity.
Training nu%2DSupport Vector Classifiers Theory and Algorithms.

Efficient test%2Dpoint selection for scan%2Dbased BIST.

A Hybrid Algorithm for Test Point Selection for Scan%2DBased BIST.
We propose a new algorithm for test point selection for scan-based BIST. The new algorithm combines the advantages of both explicit-testability-calculation and gradient techniques. The test point selection is guided bya  cost function which is partially based on explicit testability recalculation and partially on gradients. With an event-driven mechanism, it can quickly identify a set of nodes whose testability need to be recalculated due to a test point, and then use gradients to estimate the impact of the rest of the circuit. In addition, by incorporating timing information into the cost function, timing penalty caused by test points can be easily avoided. We present the results to illustrate that high fault coverages for both area- and timing-driven test point insertions can be obtained with a small number of test points. The results also indicate a signi#cant reduction of computational complexity while the qualities are similar to the explicitly-testability-calculation method.  1 I...
Timing%2DDriven Test Point Insertion for Full%2DScan and Partial%2DScan BIST.
s5378). The fault coverage for s5378 was quite a bit lower. For the circuits with a relatively small number of random-pattern-resistant faults, the results indicate that adding state-skipping logic is an efficient way to boost the fault coverage up to 100%. For the circuits that had a large number of random-pattern-resistant faults (e.g., s420 and s5378), adding state-skipping logic is not so efficient. As was described in Section IV, a more effective approach for RPR circuits would be to combine state skipping with observation-point insertion. Results are shown in Table II for combining state skipping with observation-point insertion for the RPR circuits. The observation-point procedure described in [16] was used. As can be seen from the results, adding a small number of observation points significantly reduces the amount of additional logic needed for state skipping. It should be noted that some means for observing the observation points is required, either with a condensation network [20] or an MISR (which may already exist in the boundary scan). [13] J. Carletta and C. Papachristou, “Testability analysis and insertion for RTL circuits based on pseudorandom BIST, ” in Proc. Int. Conf. Computer Design, 1995, pp. 162–167. [14] O. Coudert, “On solving covering problems, ” in Proc. 33rd Design Automation
PSBIST A Partial%2DScan Based Built%2DIn Self%2DTest Scheme.

Integration of partial scan and built%2Din self%2Dtest.

PSBIST A Partial%2DScan Based Built%2DIn Self%2DTest Scheme.

Built%2DIn Current Sensor for IDDQ Test in CMOS.

